home *** CD-ROM | disk | FTP | other *** search
/ Aminet 52 / Aminet 52 (2002)(GTI - Schatztruhe)[!][Dec 2002].iso / Aminet / game / think / AmiChess.lha / AmiChess / src / search.c < prev    next >
C/C++ Source or Header  |  2002-10-31  |  10KB  |  426 lines
  1. #include <clib/alib_protos.h>
  2. #include <mui/mui.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "common.h"
  7.  
  8. #define R 2*DEPTH
  9. #define TIMECHECK 1023
  10. #define HISTSCORE(d) ((d)*(d))
  11. #define THREATMARGIN 350
  12.  
  13. #define FUTSCORE (MATERIAL+fdel)
  14. #define GETNEXTMOVE (InChk[ply]?PhasePick1(&p,ply):PhasePick(&p,ply))
  15.  
  16. /*
  17. inline void ShowThinking(leaf *,short);
  18. inline void ShowThinking(leaf *p,short ply)
  19. {
  20. if(!(flags&POST))
  21. return;
  22. if(NodeCnt<500000&&(flags&SOLVE)) {
  23. / printf("NodeCnt=%d\n",NodeCnt);getchar();/
  24. return;
  25. }
  26. SANMove(p->move,ply);
  27. fprintf(stderr,"\r%2d. %2d/%2d%10s ",Idepth/DEPTH,
  28. (int)(p-TreePtr[ply]+1),(int)(TreePtr[ply+1]-TreePtr[ply]),SANmv);
  29. fflush(stderr);
  30. }
  31. */
  32.  
  33. static const short rank7[2]={6,1};
  34. static const short rank6[2]={5,2};
  35. static int ply1score;
  36.  
  37. int SearchRoot(short depth,int alpha,int beta)
  38. {
  39. int best,score,savealpha;
  40. short side,xside,ply,nodetype;
  41. leaf *p,*pbest;
  42. ply=1;
  43. side=board.side;
  44. xside=1^side;
  45. ChkCnt[2]=ChkCnt[1];
  46. ThrtCnt[2]=ThrtCnt[1];
  47. KingThrt[white][ply]=MateScan(white);
  48. KingThrt[black][ply]=MateScan(black);
  49. InChk[ply]=SqAtakd(board.king[side],xside);
  50. if(InChk[ply]&&ChkCnt[ply]<3*Idepth/DEPTH)
  51.     {
  52.     ChkExtCnt++;
  53.     ChkCnt[ply+1]++;
  54.     depth+=DEPTH;
  55.     }
  56. best=-INFINITY;
  57. savealpha=alpha;
  58. nodetype=PV;
  59. pbest=NULL;
  60. for(p=TreePtr[1];p<TreePtr[2];p++)
  61.     {
  62.     pick(p,1);
  63.     /* ShowThinking(p,ply); */
  64.     MakeMove(side,&p->move);
  65.     NodeCnt++;
  66.     if(p==TreePtr[1])
  67.         {
  68.         score=-Search(2,depth-DEPTH,-beta,-alpha,nodetype);
  69.         if(beta==INFINITY&&score<=alpha)
  70.             {
  71.             alpha=-INFINITY;
  72.             score=-Search(2,depth-DEPTH,-beta,-alpha,nodetype);
  73.             }
  74.         }
  75.     else
  76.         {
  77.         nodetype=CUT;
  78.         alpha=MAX(best,alpha);
  79.         score=-Search(2,depth-DEPTH,-alpha-1,-alpha,nodetype);
  80.         if(score>best)
  81.             {
  82.             if(alpha<score&&score<beta)
  83.                 {
  84.                 nodetype=PV;
  85.                 score=-Search(2,depth-DEPTH,-beta,-score,nodetype);
  86.                 }
  87.             }
  88.         }
  89.     UnmakeMove(xside,&p->move);
  90.     ply1score=p->score=score;
  91.     if(score>best)
  92.         {
  93.         best=score;
  94.         pbest=p;
  95.         if(best>alpha)
  96.             {
  97.             rootscore=best;
  98.             RootPV=p->move;
  99.             if(best>=beta) goto done;
  100.             ShowLine(RootPV,best,'&');
  101.             }
  102.         }
  103.     if(flags&TIMEOUT)
  104.         {
  105.         best=ply&1?rootscore:-rootscore;
  106.         return best;
  107.         }
  108.     if(SearchDepth==0&&(NodeCnt&TIMECHECK)==0)
  109.         {
  110.         GetElapsed();
  111.         if((et>=SearchTime&&(rootscore==-INFINITY-1||ply1score>lastrootscore-25||flags&SOLVE))||et>=maxtime) SET(flags,TIMEOUT);
  112.         }
  113. /*    if(MATE+1==best+1) return best; */
  114.     if(best==MATE) return best;
  115.     }
  116. if(best<=savealpha) TreePtr[1]->score=savealpha;
  117.  
  118. done:
  119. if(best>savealpha) history[side][pbest->move&0x0FFF]+=HISTSCORE(depth/DEPTH);
  120. rootscore=best;
  121. return best;
  122. }
  123.  
  124. int Search(short ply,short depth,int alpha,int beta,short nodetype)
  125. {
  126. int best,score,nullscore,savealpha;
  127. short side,xside,rc,t0,t1,firstmove;
  128. short fcut,fdel,donull,savenode,nullthreatdone,extend;
  129. leaf *p,*pbest;
  130. int g0,g1;
  131. int upperbound;
  132. if(EvaluateDraw()) return DRAWSCORE;
  133. if(GameCnt>=Game50+3&&Repeat())
  134.     {
  135.     RepeatCnt++;
  136.     return DRAWSCORE;
  137.     }
  138. side=board.side;
  139. xside=1^side;
  140. donull=true;
  141. extend=false;
  142. InChk[ply]=SqAtakd(board.king[side],xside);
  143. if(InChk[ply])
  144.     {
  145.     TreePtr[ply+1]=TreePtr[ply];
  146.     GenCheckEscapes(ply);
  147.     if(TreePtr[ply]==TreePtr[ply+1]) return -MATE+ply-2;
  148.     if(TreePtr[ply]+1==TreePtr[ply+1])
  149.         {
  150.         depth+=DEPTH;
  151.         extend=true;
  152.         OneRepCnt++;
  153.         }
  154.     }
  155. if(rootscore+ply>=MATE) return MATERIAL;
  156. g0=Game[GameCnt].move;
  157. g1=GameCnt>0?Game[GameCnt-1].move:0;
  158. t0=TOSQ(g0);
  159. t1=TOSQ(g1);
  160. ChkCnt[ply+1]=ChkCnt[ply];
  161. ThrtCnt[ply+1]=ThrtCnt[ply];
  162. KingThrt[white][ply]=MateScan(white);
  163. KingThrt[black][ply]=MateScan(black);
  164. if(InChk[ply]&&ply<=2*Idepth/DEPTH)
  165.     {
  166.     ChkExtCnt++;
  167.     ChkCnt[ply+1]++;
  168.     depth+=DEPTH;
  169.     extend=true;
  170.     }
  171. else if(!KingThrt[side][ply-1]&&KingThrt[side][ply]&&ply<=2*Idepth/DEPTH)
  172.     {
  173.     KingExtCnt++;
  174.     extend=true;
  175.     depth+=DEPTH;
  176.     extend=true;
  177.     donull=false;
  178.     }
  179. else if(g0&PROMOTION)
  180.     {
  181.     PawnExtCnt++;
  182.     depth+=DEPTH;
  183.     extend=true;
  184.     }
  185. else if((g0&CAPTURE)&&(board.material[computer]-board.material[1^computer]==RootMaterial))
  186.     {
  187.     RcpExtCnt++;
  188.     depth+=DEPTH;
  189.     extend=true;
  190.     }
  191. else if(depth<=DEPTH&&cboard[t0]==pawn&&(RANK(t0)==rank7[xside]||RANK(t0)==rank6[xside]))
  192.     {
  193.     PawnExtCnt++;
  194.     depth+=DEPTH;
  195.     extend=true;
  196.     }
  197. if(ply>2&&InChk[ply-1]&&cboard[t0]!=king&&t0!=t1&&!SqAtakd(t0,xside))
  198.     {
  199.     HorzExtCnt++;
  200.     depth+=DEPTH;
  201.     extend=true;
  202.     }
  203. if(depth<=0) return Quiesce(ply,alpha,beta);
  204. Hashmv[ply]=0;
  205. upperbound=INFINITY;
  206. if(flags&USEHASH)
  207.     {
  208.     rc=TTGet(side,depth,ply,alpha,beta,&score,&g1);
  209.     if(rc)
  210.         {
  211.         Hashmv[ply]=g1&MOVEMASK;
  212.         switch(rc)
  213.             {
  214.             case POORDRAFT:
  215.                 break;
  216.             case EXACTSCORE:
  217.                 return score;
  218.             case UPPERBOUND:
  219.                 beta=MIN(beta,score);
  220.                 upperbound=score;
  221.                 donull=false;
  222.                 break;
  223.             case LOWERBOUND:
  224.                 alpha=score;
  225.                 break;
  226.             case QUIESCENT:
  227.                 Hashmv[ply]=0;
  228.             }
  229.         if(alpha>=beta) return score;
  230.         }
  231.     }
  232. if(ply>4&&InChk[ply-2]&&InChk[ply-4]) donull=false;
  233. if(flags&USENULL&&g0!=NULLMOVE&&depth>DEPTH&&nodetype!=PV&&!InChk[ply]&&MATERIAL+ValueP>beta&&beta>-MATE+ply&&donull&&board.pmaterial[side]>ValueB&&!threatply)
  234.     {
  235.     TreePtr[ply+1]=TreePtr[ply];
  236.     MakeNullMove(side);
  237.     nullscore=-Search(ply+1,depth-DEPTH-R,-beta,-beta+1,nodetype);
  238.     UnmakeNullMove(xside);
  239.     if(nullscore>=beta)
  240.         {
  241.         NullCutCnt++;
  242.         return nullscore;
  243.         }
  244.     if(depth-DEPTH-R>=1&&MATERIAL>beta&&nullscore<=-MATE+256)
  245.         {
  246.         depth+=DEPTH;
  247.         extend=true;
  248.         }
  249.     }
  250. if(InChk[ply]&&TreePtr[ply]+1<TreePtr[ply+1]) SortMoves(ply);
  251. pickphase[ply]=PICKHASH;
  252. GETNEXTMOVE;
  253. fcut=false;
  254. fdel=MAX(ValueQ,maxposnscore[side]);
  255. if(!extend&&nodetype!=PV&&depth==3*DEPTH&&FUTSCORE<=alpha)
  256.     {
  257.     depth=2*DEPTH;
  258.     RazrCutCnt++;
  259.     }
  260. fdel=MAX(ValueR,maxposnscore[side]);
  261. fcut=(!extend&&nodetype!=PV&&depth==2*DEPTH&&FUTSCORE<=alpha);
  262. if(!fcut)
  263.     {
  264.     fdel=MAX(3*ValueP,maxposnscore[side]);
  265.     fcut =(nodetype!=PV&&depth==DEPTH&&FUTSCORE<=alpha);
  266.     }
  267. MakeMove(side,&p->move);
  268. NodeCnt++;
  269. g0=g1=0;
  270. while((g0=SqAtakd(board.king[side],xside))>0||(fcut&&FUTSCORE<alpha&&!SqAtakd(board.king[xside],side)&&!MateScan(xside)))
  271.     {
  272.     if(g0==0) g1++;
  273.     UnmakeMove(xside,&p->move);
  274.     if(GETNEXTMOVE==false)
  275.     return g1?Evaluate(alpha,beta):DRAWSCORE;
  276.     MakeMove(side,&p->move);
  277.     NodeCnt++;
  278.     }
  279. firstmove=true;
  280. pbest=p;
  281. best=-INFINITY;
  282. savealpha=alpha;
  283. nullthreatdone=false;
  284. nullscore=INFINITY;
  285. savenode=nodetype;
  286. if(nodetype!=PV) nodetype=(nodetype==CUT)?ALL:CUT;
  287. while(1)
  288.     {
  289.     if(firstmove)
  290.         {
  291.         firstmove=false;
  292.         score=-Search(ply+1,depth-DEPTH,-beta,-alpha,nodetype);
  293.         }
  294.     else
  295.         {
  296.         if(GETNEXTMOVE==false) break;
  297.         MakeMove(side,&p->move);
  298.         NodeCnt++;
  299.         if(SqAtakd(board.king[side],xside)) 
  300.             {
  301.             UnmakeMove(xside,&p->move);
  302.             continue;
  303.             }
  304.         if(fcut&&FUTSCORE<=alpha&&!SqAtakd(board.king[xside],side)&&!MateScan(xside))
  305.             {
  306.             UnmakeMove(xside,&p->move);
  307.             FutlCutCnt++;
  308.             NodeCnt--;
  309.             continue;
  310.             }
  311.         NodeCnt++;
  312.         if(nodetype==PV) nodetype=CUT;
  313.         alpha=MAX(best,alpha);
  314.         score=-Search(ply+1,depth-DEPTH,-alpha-1,-alpha,nodetype);
  315.         if(score>best)
  316.             {
  317.             if(savenode==PV) nodetype=PV;
  318.             if(alpha<score&&score<beta) score=-Search(ply+1,depth-DEPTH,-beta,-score,nodetype);
  319.             if(nodetype==PV&&score<=alpha&&Game[GameCnt+1].move==NULLMOVE) score=-Search(ply+1,depth-DEPTH,-alpha,INFINITY,nodetype);
  320.             }
  321.         }
  322.     UnmakeMove(xside,&p->move);
  323.     if(score>best)
  324.         {
  325.         best=score;
  326.         pbest=p;
  327.         if(best>=beta) goto done;
  328.         }
  329.     if(flags&TIMEOUT)
  330.         {
  331.         best=(ply&1?rootscore:-rootscore);
  332.         return best;
  333.         }
  334.     if(SearchDepth==0&&(NodeCnt&TIMECHECK)==0)
  335.         {
  336.         GetElapsed();
  337.         if((et>=SearchTime&&(rootscore==-INFINITY-1||ply1score>lastrootscore-25||flags&SOLVE))||et>=maxtime) SET(flags,TIMEOUT);
  338.         }
  339.     if(MATE+1==best+ply) goto done;
  340.     }
  341.  
  342. done:
  343.  
  344. /* if(upperbound<best) printf("Inconsistencies %d %d\n",upperbound,best); */
  345. if(flags&USEHASH) TTPut(side,depth,ply,savealpha,beta,best,pbest->move);
  346. if(best>savealpha) history[side][pbest->move&0x0FFF]+=HISTSCORE(depth/DEPTH);
  347. if(!(pbest->move &(CAPTURE | PROMOTION))&&best>savealpha)
  348.     {
  349.     if(killer1[ply]==0) killer1[ply]=pbest->move&MOVEMASK;
  350.     else if((pbest->move&MOVEMASK)!=killer1[ply]) killer2[ply]=pbest->move&MOVEMASK;
  351.     }
  352. return best;
  353. }
  354.  
  355. void ShowLine(int move,int score,char c)
  356. {
  357. short i;
  358. int pvar[MAXPLYDEPTH];
  359. char text[200];
  360.  
  361. if(!(flags&POST)) return;
  362. if(NodeCnt<500000&&(flags&SOLVE))
  363.     {
  364.     /* printf("NodeCnt=%d\n",NodeCnt);getchar();*/
  365.     return;
  366.     }
  367. if(Idepth==DEPTH&&c=='&') return;
  368. if(rootscore==-INFINITY-1) return;
  369. GetElapsed();
  370. text[0]=0;
  371.  
  372. if(score>MATE-255)
  373.     {
  374.     sprintf(text,"%d: %7.2f  \033bMate in %d\033n",Idepth/DEPTH,et,(MATE+2-abs(score))/2);
  375.     /* printf("\r%2d%c%7.2f Mat%02d%10ld\t",Idepth/DEPTH,c,et,eval,NodeCnt+QuiesCnt); */
  376.     }
  377. else if(score<-MATE+255)
  378.     {
  379.     sprintf(text,"%d: %7.2f  \033bMate in %d\033n",Idepth/DEPTH,et,(MATE+2-abs(score))/2);
  380.     /* printf("\r%2d%c%7.2f -Mat%02d%10ld\t",Idepth/DEPTH,c,et,eval,NodeCnt+QuiesCnt); */
  381.     }
  382. else
  383.     {
  384.     sprintf(text,"%d: %7.2f \033b%d\033n",Idepth/DEPTH,et,score);
  385.     /* printf("\r%2d%c%7.2f%7d%10ld\t",Idepth/DEPTH,c,et,score,NodeCnt+QuiesCnt); */
  386.     }
  387. if(c!='-')
  388.     {
  389.     strcat(text,"   ");
  390.     if(c=='+')
  391.         {
  392.         SANMove(RootPV,1);
  393.         strcat(text,board.side==white?MUIX_PH:MUIX_PT);
  394.         strcat(text,SANmv);
  395.         DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  396.         }
  397.     else
  398.         {
  399.         SANMove(RootPV,1);
  400.         strcat(text,board.side==white?MUIX_PH:MUIX_PT);
  401.         strcat(text,SANmv);
  402.         MakeMove(board.side,&RootPV);
  403.         TreePtr[3]=TreePtr[2];
  404.         GenMoves(2);
  405.         i=2;
  406.         pvar[1]=RootPV;
  407.         if((flags&USEHASH))
  408.             {
  409.             while(TTGetPV(board.side,i,rootscore,&pvar[i]))
  410.                 {
  411.                 if((MATESCORE(score)&&abs(score)==MATE+2-i)||Repeat()) break;
  412.                 SANMove(pvar[i],i);
  413.                 strcat(text," ");
  414.                 strcat(text,board.side==white?MUIX_PH:MUIX_PT);
  415.                 strcat(text,SANmv);
  416.                 MakeMove(board.side,&pvar[i]);
  417.                 TreePtr[i+2]=TreePtr[i+1];
  418.                 GenMoves(++i);
  419.                 }
  420.             }
  421.         DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  422.         for(--i;i;i--) UnmakeMove(board.side,&pvar[i]);
  423.         }
  424.     }
  425. }
  426.